#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    bool hasValidPath(vector<vector<char>> &grid)
    {
        int n = grid.size(), m = grid[0].size();
        if ((m + n - 1) & 1)
            return false;
        if (grid[0][0] == ')')
            return false;
        int target = (m + n - 1) / 2;
        vector<vector<vector<bool>>>
            dp(n, vector<vector<bool>>(m, vector<bool>(target + 1, false)));
        // 第 i j 位置，允许恰好多出了k个'('
        dp[0][0][1] = true;
        // cout << "0 0 1 " << dp[0][0][1] << endl;
        // if g[i][j] == ')' dp[i][j][k] = (dp[i][j-1][k+1]) || (dp[i-1][j][k+1])
        // if g[i][j] == '(' dp[i][j][k] = (dp[i][j-1][k-1]) || (dp[i-1][j][k-1])
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (i == 0 && j == 0)
                    continue;
                for (int k = 0; k <= min(target, i + j + 1); ++k)
                {
                    int nk = grid[i][j] == ')' ? (k + 1) : (k - 1);
                    if (nk < 0 || nk > min(target, i + j))
                        continue;
                    if (i > 0)
                        dp[i][j][k] = (dp[i][j][k] || dp[i - 1][j][nk]);
                    if (j > 0)
                        dp[i][j][k] = (dp[i][j][k] || dp[i][j - 1][nk]);
                    // cout << i << " " << j << " " << k << " " << dp[i][j][k] << endl;
                }
            }
        }
        return dp[n - 1][m - 1][0];
    }
};

int main()
{

    // system("pause");
    return 0;
}
